#ifndef __MOE_LIST
#define __MOE_LIST
#include <stdlib.h>
#include <iostream>

using namespace std;

template <class Element>
/**
 *  List implementation.
 *  ArrayList uses internally an array of pointers to the elements that contains
 */
class ArrayList {

private:
    Element **array;
    int size;
    int last;
    bool owner;

    static const int GROW = 50;
    static const int START = 10;

public:
    /**
    *  @param owner determines if the List is the owner of the elements, meaning that if owner is true,
    * the objects destruction it's responsability of the List, by default took the false value, so be carefull
    */
    ArrayList(bool owner = false) {
        size = START;
        array = new Element * [size];

        for (int i = 0; i < size; i++) array[i] = NULL;

        last = 0;

        this->owner = owner;
    }

    virtual ~ArrayList() {
        clean();

        delete [] array;
        array = NULL;
        size = 0;
    }


    virtual bool isOwner() {
        return owner;
    }

    virtual void setOwner(bool owner) {
        this->owner = owner;
    }

    virtual void add(Element *elementPtr) {
        if (size == last) {
            Element ** temp = new Element * [size + GROW];

            for (int i = 0; i < size + GROW; i++) {
                if (i < size) temp[i] = array[i];

                else temp[i] = NULL;
            }

            delete [] array;
            array = temp;
            temp = NULL;
            size = size + GROW;
        }

        array[last] = elementPtr;
        last++;
    }

    virtual void add(Element *elementPtr, int place) {
        if (size == last) {
            Element ** temp = new Element * [size + GROW];

            for (int i = 0; i < size + GROW; i++) {
                if (i < size) temp[i] = array[i];

                else temp[i] = NULL;
            }

            delete [] array;
            array = temp;
            temp = NULL;
            size = size + GROW;
        }

        for (int i = last - 1; i >= place; i--)
            array[i + 1] = array[i];

        array[place] = elementPtr;

        last++;
    }

    virtual void addFirst(Element *elementPtr) {

        if (size == last) {
            Element ** temp = new Element * [size + GROW];

            for (int i = 0; i < size + GROW - 1; i++) {
                if (i < size) temp[i + 1] = array[i];

                else temp[i + 1] = NULL;
            }

            temp[0] = elementPtr;
            delete [] array;
            array = temp;
            temp = NULL;
            size = size + GROW;

        } else {

            for (int j = last - 1; j >= 0; j--)
                array[j + 1] = array[j];

            array[0] = elementPtr;
        }

        last++;
    }

    /** adds at the end of the array the contents in the list
    *@param list
    */
    virtual void addAll(ArrayList<Element> *list) {

        for (int i = 0; i < list->length(); i++) add(list->get(i));

    }

    virtual Element * get(int i) {
        return array[i];
    }

    virtual Element *getLast() {
        return array[last -1];
    }

    virtual Element *getFirst() {
        return array[0];
    }

    virtual int find(Element *element) {

        for (int i = 0; i < length(); i++) if (get(i) == element) return i;

        return -1;
    }

    virtual bool contains(Element *element) {
        return (find(element) != -1);
    }
    /** releases the element by position
    * release imply that the element will be removed from the container but, not freed
    * @param i the position of the element
    * @return a pointer to the released element
    */
    virtual Element * release(int i) {
        Element * element = array[i];

        for (int j = i + 1; j < last; j++)
            array[j - 1] = array[j];

        last--;

        array[last] = NULL;

        return element;
    }

    virtual void remove(int i) {
        Element* element = release(i);

        if (owner) delete element;
    }

    virtual void remove(Element *element) {

        remove(find(element));

    }

    virtual void removeAll(ArrayList<Element> *list) {

        for (int i = 0; i < list->length(); i++) remove(list->get(i));

    }

    virtual void removeAll() {
        clean();
    }

    virtual int length() {
        return last;
    }

    virtual bool empty() {
        return last == 0;
    }

    /**

          The contents of the array are sorted in ascending order according to  a
          comparison  function  pointed  to  by  compare

          The comparison function must return an integer less than, equal to,  or
          greater  than  zero  if  the first argument is considered to be respec?
          tively less than, equal to, or greater than the second.  If two members
          compare as equal, their order in the sorted array is undefined.

          The parameters of the compare function are pointers of pointers to the
          elements in the array, so for example if you wish to  sort a ArrayList<int>
          the compare function goes like

           int compare(const void *o1, const void *o2){
               int i1 = **(int**)o1;
               int i2 = **(int**)o2;

               if (i1 < i2) return -1;

               else if (i1 == i2) return 0;

               else return 1;
           }

           @param compare the function pointer

    */
    virtual void sort(int (*compare)(const void *, const void *)) {
        qsort(array, last, sizeof (Element *), compare);
    }


protected:

    virtual void clean() {
        for (int i = 0; i < size; i++) {
            if (array[i] != NULL && owner) delete array[i];

            array[i] = NULL;
        }

        last = 0;
    }

};


#endif
